home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / expand.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  20.0 KB  |  681 lines  |  [TEXT/R*ch]
  1. /*
  2.     module: expand.c
  3.     purpose: Perform the Espresso-II Expansion Step
  4.  
  5.     The idea is to take each nonprime cube of the on-set and expand it
  6.     into a prime implicant such that we can cover as many other cubes
  7.     of the on-set.  If no cube of the on-set can be covered, then we
  8.     expand each cube into a large prime implicant by transforming the
  9.     problem into a minimum covering problem which is solved by the
  10.     heuristics of minimum_cover.
  11.  
  12.     These routines revolve around having a representation of the
  13.     OFF-set.  (In contrast to the Espresso-II manuscript, we do NOT
  14.     require an "unwrapped" version of the OFF-set).
  15.  
  16.     Some conventions on variable names:
  17.  
  18.     SUPER_CUBE is the supercube of all cubes which can be covered
  19.     by an expansion of the cube being expanded
  20.  
  21.     OVEREXPANDED_CUBE is the cube which would result from expanding
  22.     all parts which can expand individually of the cube being expanded
  23.  
  24.     RAISE is the current expansion of the current cube
  25.  
  26.     FREESET is the set of parts which haven't been raised or lowered yet.
  27.  
  28.     INIT_LOWER is a set of parts to be removed from the free parts before
  29.     starting the expansion
  30. */
  31.  
  32. #include "espresso.h"
  33.  
  34. /*
  35.     expand -- expand each nonprime cube of F into a prime implicant
  36.  
  37.     If nonsparse is true, only the non-sparse variables will be expanded;
  38.     this is done by forcing all of the sparse variables out of the free set.
  39. */
  40.  
  41. pcover expand(F, R, nonsparse)
  42. INOUT pcover F;
  43. IN pcover R;
  44. IN bool nonsparse;              /* expand non-sparse variables only */
  45. {
  46.     register pcube last, p;
  47.     pcube RAISE, FREESET, INIT_LOWER, SUPER_CUBE, OVEREXPANDED_CUBE;
  48.     int var, num_covered;
  49.     bool change;
  50.  
  51.     /* Order the cubes according to "chewing-away from the edges" of mini */
  52.     if (use_random_order)
  53.     F = random_order(F);
  54.     else
  55.     F = mini_sort(F, ascend);
  56.  
  57.     /* Allocate memory for variables needed by expand1() */
  58.     RAISE = new_cube();
  59.     FREESET = new_cube();
  60.     INIT_LOWER = new_cube();
  61.     SUPER_CUBE = new_cube();
  62.     OVEREXPANDED_CUBE = new_cube();
  63.  
  64.     /* Setup the initial lowering set (differs only for nonsparse) */
  65.     if (nonsparse)
  66.     for(var = 0; var < cube.num_vars; var++)
  67.         if (cube.sparse[var])
  68.         (void) set_or(INIT_LOWER, INIT_LOWER, cube.var_mask[var]);
  69.  
  70.     /* Mark all cubes as not covered, and maybe essential */
  71.     foreach_set(F, last, p) {
  72.     RESET(p, COVERED);
  73.     RESET(p, NONESSEN);
  74.     }
  75.  
  76.     /* Try to expand each nonprime and noncovered cube */
  77.     foreach_set(F, last, p) {
  78.     /* do not expand if PRIME or if covered by previous expansion */
  79.     if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) {
  80.  
  81.         /* expand the cube p, result is RAISE */
  82.         expand1(R, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
  83.         INIT_LOWER, &num_covered, p);
  84.         if (debug & EXPAND)
  85.         printf("EXPAND: %s (covered %d)\n", pc1(p), num_covered);
  86.         (void) set_copy(p, RAISE);
  87.         SET(p, PRIME);
  88.         RESET(p, COVERED);        /* not really necessary */
  89.  
  90.         /* See if we generated an inessential prime */
  91.         if (num_covered == 0 && ! setp_equal(p, OVEREXPANDED_CUBE)) {
  92.         SET(p, NONESSEN);
  93.         }
  94.     }
  95.     }
  96.  
  97.     /* Delete any cubes of F which became covered during the expansion */
  98.     F->active_count = 0;
  99.     change = FALSE;
  100.     foreach_set(F, last, p) {
  101.     if (TESTP(p, COVERED)) {
  102.         RESET(p, ACTIVE);
  103.         change = TRUE;
  104.     } else {
  105.         SET(p, ACTIVE);
  106.         F->active_count++;
  107.     }
  108.     }
  109.     if (change)
  110.     F = sf_inactive(F);
  111.  
  112.     free_cube(RAISE);
  113.     free_cube(FREESET);
  114.     free_cube(INIT_LOWER);
  115.     free_cube(SUPER_CUBE);
  116.     free_cube(OVEREXPANDED_CUBE);
  117.     return F;
  118. }
  119.  
  120. /*
  121.     expand1 -- Expand a single cube against the OFF-set
  122. */
  123. void expand1(BB, CC, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
  124.         INIT_LOWER, num_covered, c)
  125. pcover BB;            /* Blocking matrix (OFF-set) */
  126. pcover CC;            /* Covering matrix (ON-set) */
  127. pcube RAISE;            /* The current parts which have been raised */
  128. pcube FREESET;            /* The current parts which are free */
  129. pcube OVEREXPANDED_CUBE;    /* Overexpanded cube of c */
  130. pcube SUPER_CUBE;        /* Supercube of all cubes of CC we cover */
  131. pcube INIT_LOWER;        /* Parts to initially remove from FREESET */
  132. int *num_covered;        /* Number of cubes of CC which are covered */
  133. pcube c;            /* The cube to be expanded */
  134. {
  135.     int bestindex;
  136.  
  137.     if (debug & EXPAND1)
  138.     printf("\nEXPAND1:    \t%s\n", pc1(c));
  139.  
  140.     /* initialize BB and CC */
  141.     SET(c, PRIME);        /* don't try to cover ourself */
  142.     setup_BB_CC(BB, CC);
  143.  
  144.     /* initialize count of # cubes covered, and the supercube of them */
  145.     *num_covered = 0;
  146.     (void) set_copy(SUPER_CUBE, c);
  147.  
  148.     /* Initialize the lowering, raising and unassigned sets */
  149.     (void) set_copy(RAISE, c);
  150.     (void) set_diff(FREESET, cube.fullset, RAISE);
  151.  
  152.     /* If some parts are forced into lowering set, remove them */
  153.     if (! setp_empty(INIT_LOWER)) {
  154.     (void) set_diff(FREESET, FREESET, INIT_LOWER);
  155.     elim_lowering(BB, CC, RAISE, FREESET);
  156.     }
  157.  
  158.     /* Determine what can be raised, and return the over-expanded cube */
  159.     essen_parts(BB, CC, RAISE, FREESET);
  160.     (void) set_or(OVEREXPANDED_CUBE, RAISE, FREESET);
  161.  
  162.     /* While there are still cubes which can be covered, cover them ! */
  163.     if (CC->active_count > 0) {
  164.     select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered);
  165.     }
  166.  
  167.     /* While there are still cubes covered by the overexpanded cube ... */
  168.     while (CC->active_count > 0) {
  169.     bestindex = most_frequent(CC, FREESET);
  170.     set_insert(RAISE, bestindex);
  171.     set_remove(FREESET, bestindex);
  172.     essen_parts(BB, CC, RAISE, FREESET);
  173.     }
  174.  
  175.     /* Finally, when all else fails, choose the largest possible prime */
  176.     /* We will loop only if we decide unravelling OFF-set is too expensive */
  177.     while (BB->active_count > 0) {
  178.     mincov(BB, RAISE, FREESET);
  179.     }
  180.  
  181.     /* Raise any remaining free coordinates */
  182.     (void) set_or(RAISE, RAISE, FREESET);
  183. }
  184.  
  185. /*
  186.     essen_parts -- determine which parts are forced into the lowering
  187.     set to insure that the cube be orthognal to the OFF-set.
  188.  
  189.     If any cube of the OFF-set is distance 1 from the raising cube,
  190.     then we must lower all parts of the conflicting variable.  (If the
  191.     cube is distance 0, we detect this error here.)
  192.  
  193.     If there are essentially lowered parts, we can remove from consideration
  194.     any cubes of the OFF-set which are more than distance 1 from the
  195.     overexpanded cube of RAISE.
  196. */
  197.  
  198. void essen_parts(BB, CC, RAISE, FREESET)
  199. pcover BB, CC;
  200. pcube RAISE, FREESET;
  201. {
  202.     register pcube p, r = RAISE;
  203.     pcube lastp, xlower = cube.temp[0];
  204.     int dist;
  205.  
  206.     (void) set_copy(xlower, cube.emptyset);
  207.  
  208.     foreach_active_set(BB, lastp, p) {
  209. #ifdef NO_INLINE
  210.     if ((dist = cdist01(p, r)) > 1) goto exit_if;
  211. #else
  212.  {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1)
  213. {x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto
  214. exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||(
  215. dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube
  216. mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[
  217. var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[
  218. w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}}
  219. #endif
  220.     if (dist == 0) {
  221.         fatal("ON-set and OFF-set are not orthogonal");
  222.     } else {
  223.         (void) force_lower(xlower, p, r);
  224.         BB->active_count--;
  225.         RESET(p, ACTIVE);
  226.     }
  227. exit_if: ;
  228.     }
  229.  
  230.     if (! setp_empty(xlower)) {
  231.     (void) set_diff(FREESET, FREESET, xlower);/* remove from free set */
  232.     elim_lowering(BB, CC, RAISE, FREESET);
  233.     }
  234.  
  235.     if (debug & EXPAND1)
  236.     printf("ESSEN_PARTS:\tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
  237. }
  238.  
  239. /*
  240.     essen_raising -- determine which parts may always be added to
  241.     the raising set without restricting further expansions
  242.  
  243.     General rule: if some part is not blocked by any cube of BB, then
  244.     this part can always be raised.
  245. */
  246.  
  247. void essen_raising(BB, RAISE, FREESET)
  248. register pcover BB;
  249. pcube RAISE, FREESET;
  250. {
  251.     register pcube last, p, xraise = cube.temp[0];
  252.  
  253.     /* Form union of all cubes of BB, and then take complement wrt FREESET */
  254.     (void) set_copy(xraise, cube.emptyset);
  255.     foreach_active_set(BB, last, p)
  256.     INLINEset_or(xraise, xraise, p);
  257.     (void) set_diff(xraise, FREESET, xraise);
  258.  
  259.     (void) set_or(RAISE, RAISE, xraise);         /* add to raising set */
  260.     (void) set_diff(FREESET, FREESET, xraise);       /* remove from free set */
  261.  
  262.     if (debug & EXPAND1)
  263.     printf("ESSEN_RAISING:\tRAISE=%s FREESET=%s\n",
  264.         pc1(RAISE), pc2(FREESET));
  265. }
  266.  
  267. /*
  268.     elim_lowering -- after removing parts from FREESET, we can reduce the
  269.     size of both BB and CC.
  270.  
  271.     We mark as inactive any cube of BB which does not intersect the
  272.     overexpanded cube (i.e., RAISE + FREESET).  Likewise, we remove
  273.     from CC any cube which is not covered by the overexpanded cube.
  274. */
  275.  
  276. void elim_lowering(BB, CC, RAISE, FREESET)
  277. pcover BB, CC;
  278. pcube RAISE, FREESET;
  279. {
  280.     register pcube p, r = set_or(cube.temp[0], RAISE, FREESET);
  281.     pcube last;
  282.  
  283.     /*
  284.      *  Remove sets of BB which are orthogonal to future expansions
  285.      */
  286.     foreach_active_set(BB, last, p) {
  287. #ifdef NO_INLINE
  288.     if (! cdist0(p, r))
  289. #else
  290.  {register int w,lastw;register unsigned int x;if((lastw=cube.inword)!=-1){x=p[
  291. lastw]&r[lastw];if(~(x|x>>1)&cube.inmask)goto false;for(w=1;w<lastw;w++){x=p[w]
  292. &r[w];if(~(x|x>>1)&DISJOINT)goto false;}}}{register int w,var,lastw;register
  293. pcube mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.
  294. var_mask[var];lastw=cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++)
  295. if(p[w]&r[w]&mask[w])goto nextvar;goto false;nextvar:;}}continue;false:
  296. #endif
  297.         BB->active_count--, RESET(p, ACTIVE);
  298.     }
  299.  
  300.  
  301.     /*
  302.      *  Remove sets of CC which cannot be covered by future expansions
  303.      */
  304.     if (CC != (pcover) NULL) {
  305.     foreach_active_set(CC, last, p) {
  306. #ifdef NO_INLINE
  307.         if (! setp_implies(p, r))
  308. #else
  309.         INLINEsetp_implies(p, r, /* when false => */ goto false1);
  310.         /* when true => go to end of loop */ continue;
  311.         false1:
  312. #endif
  313.         CC->active_count--, RESET(p, ACTIVE);
  314.     }
  315.     }
  316. }
  317.  
  318. /*
  319.     most_frequent -- When all else fails, select a reasonable part to raise
  320.     The active cubes of CC are the cubes which are covered by the
  321.     overexpanded cube of the original cube (however, we know that none
  322.     of them can actually be covered by a feasible expansion of the
  323.     original cube).  We resort to the MINI strategy of selecting to
  324.     raise the part which will cover the same part in the most cubes of CC.
  325. */
  326. int most_frequent(CC, FREESET)
  327. pcover CC;
  328. pcube FREESET;
  329. {
  330.     register int i, best_part, best_count, *count;
  331.     register pset p, last;
  332.  
  333.     /* Count occurences of each variable */
  334.     count = ALLOC(int, cube.size);
  335.     for(i = 0; i < cube.size; i++)
  336.     count[i] = 0;
  337.     if (CC != (pcover) NULL)
  338.     foreach_active_set(CC, last, p)
  339.         set_adjcnt(p, count, 1);
  340.  
  341.     /* Now find which free part occurs most often */
  342.     best_count = best_part = -1;
  343.     for(i = 0; i < cube.size; i++)
  344.     if (is_in_set(FREESET,i) && count[i] > best_count) {
  345.         best_part = i;
  346.         best_count = count[i];
  347.     }
  348.     FREE(count);
  349.  
  350.     if (debug & EXPAND1)
  351.     printf("MOST_FREQUENT:\tbest=%d FREESET=%s\n", best_part, pc2(FREESET));
  352.     return best_part;
  353. }
  354.  
  355. /*
  356.     setup_BB_CC -- set up the blocking and covering set families;
  357.  
  358.     Note that the blocking family is merely the set of cubes of R, and
  359.     that CC is the set of cubes of F which might possibly be covered
  360.     (i.e., nonprime cubes, and cubes not already covered)
  361. */
  362.  
  363. void setup_BB_CC(BB, CC)
  364. register pcover BB, CC;
  365. {
  366.     register pcube p, last;
  367.  
  368.     /* Create the block and cover set families */
  369.     BB->active_count = BB->count;
  370.     foreach_set(BB, last, p)
  371.     SET(p, ACTIVE);
  372.  
  373.     if (CC != (pcover) NULL) {
  374.     CC->active_count = CC->count;
  375.     foreach_set(CC, last, p)
  376.         if (TESTP(p, COVERED) || TESTP(p, PRIME))
  377.         CC->active_count--, RESET(p, ACTIVE);
  378.         else
  379.         SET(p, ACTIVE);
  380.     }
  381. }
  382.  
  383. /*
  384.     select_feasible -- Determine if there are cubes which can be covered,
  385.     and if so, raise those parts necessary to cover as many as possible.
  386.  
  387.     We really don't check to maximize the number that can be covered;
  388.     instead, we check, for each fcc, how many other fcc remain fcc
  389.     after expanding to cover the fcc.  (Essentially one-level lookahead).
  390. */
  391.  
  392. void select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered)
  393. pcover BB, CC;
  394. pcube RAISE, FREESET, SUPER_CUBE;
  395. int *num_covered;
  396. {
  397.     register pcube p, last, bestfeas, *feas;
  398.     register int i, j;
  399.     pcube *feas_new_lower;
  400.     int bestcount, bestsize, count, size, numfeas, lastfeas;
  401.     pcover new_lower;
  402.  
  403.     /*  Start out with all cubes covered by the over-expanded cube as
  404.      *  the "possibly" feasibly-covered cubes (pfcc)
  405.      */
  406.     feas = ALLOC(pcube, CC->active_count);
  407.     numfeas = 0;
  408.     foreach_active_set(CC, last, p)
  409.     feas[numfeas++] = p;
  410.  
  411.     /* Setup extra cubes to record parts forced low after a covering */
  412.     feas_new_lower = ALLOC(pcube, CC->active_count);
  413.     new_lower = new_cover(numfeas);
  414.     for(i = 0; i < numfeas; i++)
  415.     feas_new_lower[i] = GETSET(new_lower, i);
  416.  
  417.  
  418. loop:
  419.     /* Find the essentially raised parts -- this might cover some cubes
  420.        for us, without having to find out if they are fcc or not
  421.     */
  422.     essen_raising(BB, RAISE, FREESET);
  423.  
  424.     /* Now check all "possibly" feasibly covered cubes to check feasibility */
  425.     lastfeas = numfeas;
  426.     numfeas = 0;
  427.     for(i = 0; i < lastfeas; i++) {
  428.     p = feas[i];
  429.  
  430.     /* Check active because essen_parts might have removed it */
  431.     if (TESTP(p, ACTIVE)) {
  432.  
  433.         /*  See if the cube is already covered by RAISE --
  434.          *  this can happen because of essen_raising() or because of
  435.          *  the previous "loop"
  436.          */
  437.         if (setp_implies(p, RAISE)) {
  438.         (*num_covered) += 1;
  439.         (void) set_or(SUPER_CUBE, SUPER_CUBE, p);
  440.         CC->active_count--;
  441.         RESET(p, ACTIVE);
  442.         SET(p, COVERED);
  443.         /* otherwise, test if it is feasibly covered */
  444.         } else if (feasibly_covered(BB,p,RAISE,feas_new_lower[numfeas])) {
  445.         feas[numfeas] = p;            /* save the fcc */
  446.         numfeas++;
  447.         }
  448.     }
  449.     }
  450.     if (debug & EXPAND1)
  451.     printf("SELECT_FEASIBLE: started with %d pfcc, ended with %d fcc\n",
  452.         lastfeas, numfeas);
  453.  
  454.     /* Exit here if there are no feasibly covered cubes */
  455.     if (numfeas == 0) {
  456.     FREE(feas);
  457.     FREE(feas_new_lower);
  458.     free_cover(new_lower);
  459.     return;
  460.     }
  461.  
  462.     /* Now find which is the best feasibly covered cube */
  463.     bestcount = 0;
  464.     bestsize = 9999;
  465.     for(i = 0; i < numfeas; i++) {
  466.     size = set_dist(feas[i], FREESET);    /* # of newly raised parts */
  467.     count = 0;    /* # of other cubes which remain fcc after raising */
  468.  
  469. #define NEW
  470. #ifdef NEW
  471.     for(j = 0; j < numfeas; j++)
  472.         if (setp_disjoint(feas_new_lower[i], feas[j]))
  473.         count++;
  474. #else
  475.     for(j = 0; j < numfeas; j++)
  476.         if (setp_implies(feas[j], feas[i]))
  477.         count++;
  478. #endif
  479.     if (count > bestcount) {
  480.         bestcount = count;
  481.         bestfeas = feas[i];
  482.         bestsize = size;
  483.     } else if (count == bestcount && size < bestsize) {
  484.         bestfeas = feas[i];
  485.         bestsize = size;
  486.     }
  487.     }
  488.  
  489.     /* Add the necessary parts to the raising set */
  490.     (void) set_or(RAISE, RAISE, bestfeas);
  491.     (void) set_diff(FREESET, FREESET, RAISE);
  492.     if (debug & EXPAND1)
  493.     printf("FEASIBLE:  \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
  494.     essen_parts(BB, CC, RAISE, FREESET);
  495.     goto loop;
  496. /* NOTREACHED */
  497. }
  498.  
  499. /*
  500.     feasibly_covered -- determine if the cube c is feasibly covered
  501.     (i.e., if it is possible to raise all of the necessary variables
  502.     while still insuring orthogonality with R).  Also, if c is feasibly
  503.     covered, then compute the new set of parts which are forced into
  504.     the lowering set.
  505. */
  506.  
  507. bool feasibly_covered(BB, c, RAISE, new_lower)
  508. pcover BB;
  509. pcube c, RAISE, new_lower;
  510. {
  511.     register pcube p, r = set_or(cube.temp[0], RAISE, c);
  512.     int dist;
  513.     pcube lastp;
  514.  
  515.     set_copy(new_lower, cube.emptyset);
  516.     foreach_active_set(BB, lastp, p) {
  517. #ifdef NO_INLINE
  518.     if ((dist = cdist01(p, r)) > 1) goto exit_if;
  519. #else
  520.  {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1)
  521. {x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto
  522. exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||(
  523. dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube
  524. mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[
  525. var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[
  526. w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}}
  527. #endif
  528.     if (dist == 0)
  529.         return FALSE;
  530.     else
  531.         (void) force_lower(new_lower, p, r);
  532.     exit_if: ;
  533.     }
  534.     return TRUE;
  535. }
  536.  
  537. /*
  538.     mincov -- transform the problem of expanding a cube to a maximally-
  539.     large prime implicant into the problem of selecting a minimum
  540.     cardinality cover over a family of sets.
  541.  
  542.     When we get to this point, we must unravel the remaining off-set.
  543.     This may be painful.
  544. */
  545.  
  546. void mincov(BB, RAISE, FREESET)
  547. pcover BB;
  548. pcube RAISE, FREESET;
  549. {
  550.     int expansion, nset, var, dist;
  551.     pset_family B;
  552.     register pcube xraise=cube.temp[0], xlower, p, last, plower;
  553.  
  554. #ifdef RANDOM_MINCOV
  555.     dist = random() % set_ord(FREESET);
  556.     for(var = 0; var < cube.size && dist >= 0; var++) {
  557.     if (is_in_set(FREESET, var)) {
  558.         dist--;
  559.     }
  560.     }
  561.  
  562.     set_insert(RAISE, var);
  563.     set_remove(FREESET, var);
  564.     (void) essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET);
  565. #else
  566.  
  567.     /* Create B which are those cubes which we must avoid intersecting */
  568.     B = new_cover(BB->active_count);
  569.     foreach_active_set(BB, last, p) {
  570.     plower = set_copy(GETSET(B, B->count++), cube.emptyset);
  571.     (void) force_lower(plower, p, RAISE);
  572.     }
  573.  
  574.     /* Determine how many sets it will blow up into after the unravel */
  575.     nset = 0;
  576.     foreach_set(B, last, p) {
  577.     expansion = 1;
  578.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  579.         if ((dist=set_dist(p, cube.var_mask[var])) > 1) {
  580.         expansion *= dist;
  581.         if (expansion > 500) goto heuristic_mincov;
  582.         }
  583.     }
  584.     nset += expansion;
  585.     if (nset > 500) goto heuristic_mincov;
  586.     }
  587.  
  588.     B = unravel(B, cube.num_binary_vars);
  589.     xlower = do_sm_minimum_cover(B);
  590.  
  591.     /* Add any remaining free parts to the raising set */
  592.     (void) set_or(RAISE, RAISE, set_diff(xraise, FREESET, xlower));
  593.     (void) set_copy(FREESET, cube.emptyset);    /* free set is empty */
  594.     BB->active_count = 0;            /* BB satisfied */
  595.     if (debug & EXPAND1) {
  596.     printf("MINCOV:    \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
  597.     }
  598.     sf_free(B);
  599.     set_free(xlower);
  600.     return;
  601.  
  602. heuristic_mincov:
  603.     sf_free(B);
  604.     /* most_frequent will pick first free part */
  605.     set_insert(RAISE, most_frequent(/*CC*/ (pcover) NULL, FREESET));
  606.     (void) set_diff(FREESET, FREESET, RAISE);
  607.     essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET);
  608.     return;
  609. #endif
  610. }
  611.  
  612. /*
  613.     find_all_primes -- find all of the primes which cover the
  614.     currently reduced BB
  615. */
  616. pcover find_all_primes(BB, RAISE, FREESET)
  617. pcover BB;
  618. register pcube RAISE, FREESET;
  619. {
  620.     register pset last, p, plower;
  621.     pset_family B, B1;
  622.  
  623.     if (BB->active_count == 0) {
  624.     B1 = new_cover(1);
  625.     p = GETSET(B1, B1->count++);
  626.     (void) set_copy(p, RAISE);
  627.     SET(p, PRIME);
  628.     } else {
  629.     B = new_cover(BB->active_count);
  630.     foreach_active_set(BB, last, p) {
  631.         plower = set_copy(GETSET(B, B->count++), cube.emptyset);
  632.         (void) force_lower(plower, p, RAISE);
  633.     }
  634.     B = sf_rev_contain(unravel(B, cube.num_binary_vars));
  635.     B1 = exact_minimum_cover(B);
  636.     foreach_set(B1, last, p) {
  637.         INLINEset_diff(p, FREESET, p);
  638.         INLINEset_or(p, p, RAISE);
  639.         SET(p, PRIME);
  640.     }
  641.     free_cover(B);
  642.     }
  643.     return B1;
  644. }
  645.  
  646. /*
  647.     all_primes -- foreach cube in F, generate all of the primes
  648.     which cover the cube.
  649. */
  650.  
  651. pcover all_primes(F, R)
  652. pcover F, R;
  653. {
  654.     register pcube last, p, RAISE, FREESET;
  655.     pcover Fall_primes, B1;
  656.  
  657.     FREESET = new_cube();
  658.     RAISE = new_cube();
  659.     Fall_primes = new_cover(F->count);
  660.  
  661.     foreach_set(F, last, p) {
  662.     if (TESTP(p, PRIME)) {
  663.         Fall_primes = sf_addset(Fall_primes, p);
  664.     } else {
  665.         /* Setup for call to essential parts */
  666.         (void) set_copy(RAISE, p);
  667.         (void) set_diff(FREESET, cube.fullset, RAISE);
  668.         setup_BB_CC(R, /* CC */ (pcover) NULL);
  669.         essen_parts(R, /* CC */ (pcover) NULL, RAISE, FREESET);
  670.  
  671.         /* Find all of the primes, and add them to the prime set */
  672.         B1 = find_all_primes(R, RAISE, FREESET);
  673.         Fall_primes = sf_append(Fall_primes, B1);
  674.     }
  675.     }
  676.  
  677.     set_free(RAISE);
  678.     set_free(FREESET);
  679.     return Fall_primes;
  680. }
  681.